#include <vector>
#include <iostream>

using namespace std;

void split(vector<int> & input, int left, int right);
void merge(vector<int> & input, int left, int mid, int right);

void sort(vector<int> & input){
	int len = input.size();
	split(input, 0, len-1);
}

void split(vector<int> & input, int left, int right){
	if(left < right){
		int mid = (left + right) / 2;
		split(input, left, mid);
		split(input, mid + 1, right);
		merge(input, left, mid, right);
	}
}

void merge(vector<int> & input, int left, int mid, int right){
	vector<int> tmp;
	tmp.reserve(right-left);
	int i = left, j = mid + 1;
	while(i <= mid && j <= right){
		if(input[i] <= input[j]){
			tmp.push_back(input[i++]);
		}else{
			tmp.push_back(input[j++]);
		}
	}
	while(i <= mid){
		tmp.push_back(input[i++]);
	}
	while(j <= right){
		tmp.push_back(input[j++]);
	}
	i = 0;
	while(left <= right){
		input[left++] = tmp[i++];
	}
}


int main(){
	vector<int> input = {3,4,1,2,44,9,1,5,7,8};
	for(auto i : input){
		cout << i << ",";
	}
	cout << endl;
	sort(input);
	for(auto i : input){
		cout << i << ",";
	}
	cout << endl;
	
	return 0;
}